#include <iostream>

using namespace std;

// 707. 设计链表
// 你可以选择使用单链表或者双链表，设计并实现自己的链表。
// 单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。
// https://leetcode.cn/problems/design-linked-list/
// Singly Linked List
// Without dummyHead;

class MyLinkedList {
private:
    class Node {
    public:
        int val;
        Node* next;
        Node(int val, Node* next): val(val), next(next) {}
        Node(int val): Node(val, NULL) {}
    };
    Node* head;
public:
    /** Initialize your data structure here. */
    MyLinkedList() {
        head = NULL;
    }

    /** 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。 */
    int get(int index) {

        Node* cur = head;
        for(int i = 0; i < index && cur; i++)
            cur = cur->next;

        if(!cur) return -1;
        return cur->val;
    }
    /** 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。 */
    void addAtHead(int val) {
        head = new Node(val, head);
    }
    /** 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。 */
    void addAtTail(int val) {
        if(head == NULL)
            head = new Node(val);
        else {
            Node* pre = head;
            while(pre->next)
                pre = pre->next;
            pre->next = new Node(val);
        }
    }
    /** 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
     * 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。 */
    void addAtIndex(int index, int val) {
        if(index == 0)
            addAtHead(val);
        else {
            Node* pre = head;
            for(int i = 1; i < index && pre; i++)
                pre = pre->next;

            if(pre)
                pre->next = new Node(val, pre->next);
        }
    }
    /** 如果下标有效，则删除链表中下标为 index 的节点。 */
    void deleteAtIndex(int index) {
        // 要删除的第0个元素，头结点
        if(index == 0) {
            if(head) {
                Node* delNode = head;
                head = head->next;
                delete delNode;
            }
        } else {
            Node* pre = head;
            for(int i = 1; i < index && pre; i++)
                pre = pre->next;

            if(pre && pre->next) {
                Node* delNode = pre->next;
                pre->next = delNode->next;
                delete delNode;
            }
        }
    }
};


int main() {
    /**
     * Your MyLinkedList object will be instantiated and called as such:
     * MyLinkedList* obj = new MyLinkedList();
     * int param_1 = obj->get(index);
     * obj->addAtHead(val);
     * obj->addAtTail(val);
     * obj->addAtIndex(index,val);
     * obj->deleteAtIndex(index);
     */
    MyLinkedList* obj = new MyLinkedList();
    obj->addAtHead(1);
    obj->addAtTail(3);
    obj->addAtIndex(1, 2);  // 链表变为 1->2->3
    cout << obj->get(1) << endl;    // 返回 2
    obj->deleteAtIndex(1);  // 现在链表变为1->3
    cout << obj->get(1) << endl;    // 返回 3
    cout << obj->get(-2) << endl;   // 小于0，返回第0个元素。这是错误的
    cout << obj->get(3) << endl;    // 超出链表范围，返回-1

    return 0;
}
